/*
 * @Author: lei
 * @Description: 快速排序示例
 * @FilePath: /new/quicksort.cc
 */
#include <iostream>

#include "sort.h"
using namespace std;
// g++ -o quicksort quicksort.cc -std=c++11

// 1. 选取pivot
// 2. 实现分区算法，左右两边摆
// 3. 对两边的分区同样采用1，2两步

// 分区算法不同实现步骤
int Partition(vector<int>& v, int start, int end) {
  // 选取随机元素作为pivot
  int random_index = start + rand() % (end - start + 1);
  swap(v[random_index], v[start]);

  int pivot = v[start];
  int l = start + 1;
  int r = end;
  while (l < r) {
    while (l < r && v[l] <= pivot) l++;
    while (l < r && v[r] >= pivot) r--;
    swap(v[l], v[r]);
  }
  if (l == r && v[r] > pivot) r--;
  swap(v[start], v[r]);
  // swap(v[r],pivot);错误！！！！v[start]处没有填到正确的值
  return r;
}
// 是v[start]不是v[0]!

// [l,r]为待排序元素闭区间
void QuickSort(vector<int>& v, int l, int r) {
  if (l >= r) return;
  int mid = Partition(v, l, r);
  QuickSort(v, l, mid - 1);
  QuickSort(v, mid + 1, r);
}

// int main() {
//   vector<int> v{1, 8, 3, 89, 0, -342, 90, -87, 987, 6};
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   QuickSort(v, 0, v.size() - 1);
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   return 0;
// }

// 时间复杂度：最佳、平均O(NlogN)，最差O(N^2)
// 空间复杂度：O(N)